package 剑指offer;

public class Offer63_JZ {
    // 股票最大利润
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n==0) {
            return 0;
        }
        // base case, dp[i][0]=0, dp[i][1] = Integer.MIN_VALUE
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for(int i=0; i<n; i++) {
            // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            // dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
            dp_i_1 = Math.max(dp_i_1, -prices[i]);
        }
        return dp_i_0;
    }
}
